1. Field of the Invention
The present invention relates to a router apparatus which routes and transmits a packet, which is received from a packet switching network, e.g., the Internet through an input port circuit, to each adjacent node through each output port circuit, and relates the output port circuit of the router apparatus and a method of controlling the output port circuit thereof. In particular, the present invention relates to an output port circuit of a router apparatus that controls storage and reading out of a packet into and from a buffer memory of the output port circuit thereof, and a method of controlling the output port circuit thereof.
2. Description of the Related Art
Recently, as high-performance computers have begun to fulfill their functions as new information equipment in not only research organizations and businesses but also in the general consumer area, the use of network applications such as the WWW has remarkably increased, and this leads to that the traffic in the Internet and Intranet have rapidly and exponentially increased. Integration of voice traffic into conventional data traffic on the Internet, that is VoIP (Voice over IP) has begun in earnest. It is expected in the future that various types of traffic coexist which require different communication qualities such as stream type traffic having a fixed transfer speed like video and traffic for high-speed data transfer.
Accordingly, techniques including Diff-Serv (Differentiated Service) and MPLS (Multi-Protocol Label Switching) have been proposed and spread. The Diff-Serv defines different service classes for traffic having different attributes and requires an Internet router to offer services best suitable for the respective classes. The MPLS is a technique for accelerating a packet transfer speed. In order to realize differentiated services, a header of the MPLS packet includes a CoS (Class of Service) field. It is practical in the present communication situation to provide a repeater apparatus such as a router apparatus with a control function so as to realize a QoS (Quality of Service) control mechanism that guarantees diversified qualities under these circumstances. Further, following the recent acceleration of network speed, it is essential to allow the QoS control mechanism to operate at a high speed in the router apparatus.
A study of buffer memory read scheduling has been actively conducted as one of the techniques that are proposed to provide the QoS guarantee mechanism as mentioned above or a class-based priority control mechanism. For example, in an input and output buffer switch that arranges buffer memories at input and output ports, respectively, the problem of the static occupation of an output circuit by specific connections can be improved by a buffer memory read scheduling criterion such as Weighted Fair Queuing (WFQ), Weighted Round Robin (WRR), etc. However, it is impossible to ensure storing a high-priority traffic packet that arrives when a buffer load is high only by the use of one of these scheduling criterions, and it is difficult to realize QoS guarantee. In addition, it is highly likely that a plurality of ports is connected with an interface card of the router apparatus. If so, a buffer memory space is shared among the ports. However, no sufficient consideration has been given to buffer memory management that assumes connection of a plurality of ports. In a prior art document of Katsuya Minami et. al, “Per-Flow Buffer Management Scheme with Class-based Priority in the Internet Router”, the Technical Report of The Institute of Electronics, Information and Communication Engineers in Japan (hereinafter referred to as “IEICE”), SSE99-175, IN99-138, issued by IEICE, pp. 85-90, March 2000, for example, there is proposed one method of dealing with this problem, which method will be referred to as “prior art” hereinafter.
A conventional method of managing a buffer memory will be described. A router apparatus logically secures a minimum size of a buffer memory which can be used by each flow (hereinafter, referred to as a “basic volume”). In an environment in which a buffer memory utilization rate is low, each flow is allowed to use an actually necessary storage area of the buffer memory irrespective of this basic volume. If this environment changes to a high-load environment and the buffer memory turns full, the router apparatus applies a pushout mechanism and discards (that is, pushes out) a specific packet in the buffer memory. The conventional method is used on the assumption of an environment in which one buffer memory is shared among a plurality of ports. Accordingly, in the conventional method, the basic volume is managed hierarchically in the order of ports, classes and flows and the WRR is hierarchically carried out as a scheduling criterion. Further, in the conventional method, bandwidth allocation is carried out so as to realize class-based priority control.
A conventional method of allocating basic volumes will be described. When the router apparatus senses a flow, a basic volume of the buffer memory in the router apparatus is allocated to the flow. The allocation method is as follows.
First of all, a total buffer memory size of the router apparatus is shared among a plurality of ports according to line speed ratios. Next, a fixed, necessary buffer memory volume calculated from a guaranteed bandwidth is allocated to flows that belong to a bandwidth-guaranteed (BG) class, irrespective of the basic volume allocated to the port to which the flow belongs. To each of flows that belong to the other best effort classes, volumes obtained by subtracting allocation volumes for the bandwidth-guaranteed class from the basic volume for the ports are allocated according to predetermined weighting factors. The allocated basic volume changes according to the detection of the flow and the discard of the flow. Namely, the basic volume is allocated only to the flows that actually use the buffer memory.
The allocation method will be concretely described with reference to FIG. 47. FIG. 47 is a schematic explanatory view for explaining a conventional method of allocating a storage area of the buffer memory. First of all, the router apparatus allocates a total buffer memory volume, i.e., buffer memory volumes p1, P2, . . . and PN to respective ports P1 to PN according to output line speed ratios, respectively. In the case of FIG. 47, the basic volume p1 is allocated first to the port P1. Next, the basic volume p1 is shared among classes that belong to the port P1. Allocation ratios of the classes dynamically change. This is because the router apparatus allocates the basic volume according to a reserved volume for the bandwidth-guaranteed class C2, to the class C2. The other classes of C1 and C0 are allocated a remaining volume of the basic volume p1 according to their predetermined class weighting factors. In the case of FIG. 47, a necessary buffer memory volume α1 calculated from a reserved bandwidth is allocated first to the bandwidth-guaranteed class C2. This necessary buffer memory volume is a quantity with which all the packets of reserved traffic in a unit time interval that arrive in a burst at the router apparatus can be stored. Thereafter, a remaining buffer memory volume (p1-α1) is allocated to the other classes. Procedures for the allocation are as follows. Priorities w11 and w10 and detected number of flows f11 and f10 of respective classes are used to obtain products of the priorities and the number of flows as weighting factors of the respective classes. The products are applied to the buffer memory volume (p1-α1). In the case of the port P1 in FIG. 47, a weighting factor Wc1 of the class C1 and a weighting factor Wc0 of the class C0 are defined by the following Equations (1) and (2), respectively:Wc1=f11×w11  (1)Wc0=f10×w10  (2).
A ratio of the weighting factors Wc1 to Wc0 is applied to the buffer memory volume (p1-α1) to acquire basic volumes of the classes C0 and C1. Namely, the basic volumes β1 and γ1 of the classes C1 and C0 are expressed by the following Equations (3) and (4), respectively:
                              β          1                =                              (                          p1              -              α1                        )                    ×                                    W              C1                                                      W                C1                            +                              W                C0                                                                        (        3        )                                          γ          1                =                              (                          p1              -              α1                        )                    ×                                    W              C0                                                      W                C1                            +                              W                C0                                                                        (        4        )            
On the other hand, if a packet arrives at the router apparatus when the buffer memory is full, the router apparatus carries out the following operation as a pushout mechanism of discarding an excessive packet.
If a new packet that belongs to a flow that uses the buffer memory beyond its basic volume arrives, the packet is discarded as it is. If a packet that belongs to a flow that uses the buffer memory below its basic volume, the router apparatus employs the pushout mechanism to permit the packet arriving at the buffer memory to be stored in the buffer memory. When a pushout object packet search is finished, the arrived packet is overwritten on a pushout object packet at a position of the buffer memory at which the pushout object packet is present and the overwritten packet (that is, the pushout object packet) is discarded. If the pushout object packet search reveals that there is no flow that uses the buffer memory beyond its basic volume, the arrived packet is discarded.
According to the prior art, the basic volume is allocated hierarchically, so that the pushout object flow search is carried out in the following procedures. First of all, the router apparatus checks whether the class to which the arrived packet belongs uses the buffer memory beyond its basic volume. If the class uses the buffer memory beyond its basic volume, a flow that most exceeds its basic volume in the class is to be pushed out. If the class uses the buffer memory within its basic volume, the router apparatus checks an excessively used volume for the port to which the arrived packet belongs. If there are classes the used volumes of which exceed their basic volumes, the router apparatus decides the class having the most excessively used volume among the classes. Next, the router apparatus determines the flow having the most excessively used volume in the class. If used volumes of none of the classes exceed their basic volumes, the router apparatus conducts a similar search in the port having the most excessively used volume.
The pushout object flow is searched by the above-mentioned method, and the arrived packet is permitted to be overwritten on a head packet of the flow. This method will be described concretely with reference to FIGS. 48A and 48B. FIGS. 48A and 48B are schematic explanatory views for explaining a method of discarding a packet in a class that uses the storage area of the buffer memory allocated to the class as shown in FIG. 47. FIG. 48A shows that a packet in a different class from that of the arrived packet at the same port is discarded. FIG. 48B shows that a packet in a class at a different port from that of the arrived packet is discarded.
In FIGS. 48A and 48B, solid-line circles surrounding the ports P1 to P3 and the classes C1 to C3 in the ports indicate basic volumes of the ports and classes, respectively, and dotted-line circuits thereof indicate actually used volumes of the ports and classes, respectively. In FIG. 48A, it is assumed that the flow to which the arrived packet belongs does not use the storage area of the buffer memory larger than its basic volume. The excessively used volume of the class C3 to which the arrived flow belongs at that time is checked. In the case of FIG. 48A, the used volume (indicated by the dotted-line circle) of the class C3 in the port P1 does not exceed its basic volume (indicated by the solid-line circle), so that the excessively used volume of the port to which the class C3 belongs is checked. The port P1 uses the storage area larger than its basic volume. Therefore, the pushout object class is among the classes that belong to the port P1, i.e., the class C2 having the most excessively used volume among the classes. In this method, flow-based control is carried out. Due to this, the pushout object packet is a head packet of the flow having the most excessively used volume among the flows that belong to the class C2.
Further, a search is conducted in the case of FIG. 48B in a manner similar to that of FIG. 48A. Referring to FIG. 48B, the port P1 to which the arrived flow belongs uses the storage area of the buffer memory within its basic volume (indicated by the solid-line circuit). In that case, the pushout object is the port P3 having the most excessively used volume and the router apparatus conducts a search similar to the above-mentioned search to flows that belong to the port P3. A result of the search reveals that the pushout object is the class C1 having the most excessively used volume in the port P3.
The conventional scheduling criterion and bandwidth allocation method will next be described. FIG. 49 is a schematic explanatory view for explaining hierarchically allocating all bandwidths available for transmission to ports, classes and flows. According to the conventional method, the WRR is executed in the order of ports, classes and flows as a reading out scheduling criterion for packets stored in the buffer memory.
If the WRR is executed, it is necessary to set weighting factors of the respective classes. A decision method for the weighting factors will be described. In the WRR for the first hierarchy, i.e., ports, the router apparatus sets an output line speed ratio of the ports as a weighting factor of the ports. In the WRR for the second hierarchy, i.e., classes, the router apparatus allocates a bandwidth guaranteed for a bandwidth-guaranteed flow from a total link capacity. A remaining link capacity after the allocation of the bandwidth to the bandwidth-guaranteed flow is shared among the classes other than the bandwidth-guaranteed class. As the allocation ratio, the class ratio used upon allocating the basic volume is employed. A bandwidth allocation volume calculated based on the ratio are converted to a simple integer ratio, thus obtaining a weighting factor. In the WRR for the third hierarchy, i.e., flows, the route apparatus utilizes a reserved bandwidth ratio as a weighting factor of each flow in the bandwidth-guaranteed class. As for the other classes, the router apparatus gives a weighting factor of “1” to each flow so as to keep fairness in the flows. Namely, round robin (RR) is employed as a scheduling criterion for flows in low priority classes other than the bandwidth-guaranteed class.
As described above, according to the prior art, if the router apparatus maintains the storage area of the buffer memory allocated to the arrived packet for each class to which packets belong, the performance of the router apparatus is disadvantageously unstable. Therefore, it is necessary to set a more appropriate processing unit for the management of the storage area of the buffer memory.
In order to solve the above-mentioned technical disadvantage, it is necessary to realize a high-performance router apparatus in which a QoS control mechanism including an appropriate buffer management mechanism for each flow is provided. In particular, it is necessary to provide a service suitable for each class or each flow and realize high-level QoS guarantee even if a load of a buffer memory of the router apparatus is high.
Moreover, in order to actually execute the management of the buffer memory of the router apparatus, it is necessary to manage a location of an arrived packet in the buffer memory. In this case, the problem arises that a packet transmitted on the Internet has a variable length. In the buffer memory, a packet storage start position and the packet length need to be maintained. However, if the storage and transmission of the variable-length packet are repeated, free spaces in the buffer memory disadvantageously are dispersed. This disadvantageously complicates the management of the buffer memory and the packets.